package data_structure.sequence_list;

import java.util.ArrayList;
import java.util.List;

    public class 关于链表的操作但本身不是一个链表3 {
        // 创建链表
        // int[] -> Node head
        public static Node 根据数组创建链表() {
            // TODO:
            return null;
        }

        public static Node 手动去创建结点然后构建链表() {
            Node n1 = new Node(100);
            Node n2 = new Node(200);
            Node n3 = new Node(300);
            Node n4 = new Node(400);
            Node n5 = new Node(500);
            Node n6 = new Node(600);

            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = n5;
            n5.next = n6;
            n6.next = null;

            return n1;
        }

        // 链表的遍历操作
        public static void 遍历一条链表_打印链表中的每个元素(Node head) {
            // 参数 head，是我们手上的唯一线索，如何完成链表的遍历？
            // 需要循环完成，拿什么作为遍历时的 内容 进行

            Node cur = head;        // 让 cur 指向 head 指向的对象（链表的头结点对象）
            while (cur != null) {
                // 此处，cur 分别经过了链表的所有结点【注意：在 cur = cur.next】
                // 结点和元素是一一对应的
                int element = cur.val;  // element 经历了链表中的每个元素
                System.out.println(element);

                cur = cur.next;
            }

            // cur 会经历链表中的每个结点：按照从前往后的顺序，每个结点只会经过一次
        }

        private static int 统计链表中的元素个数(Node head) {
            // 链表链表中的每个元素，计数
            int count = 0;
            for (Node cur = head; cur != null; cur = cur.next) {
                count++;    // 每个结点都会经过一次，所以每个元素都会经过一次，count++ 会被指向元素个数次
            }

            return count;   // 元素的个数
        }

        // 从前到后找到的第一个
        private static Node 查找链表中某个元素所在的结点(Node head, int target) {
            // 所谓从前到后查找，就是要遍历链表中的每个元素，和 target 进行对比
            Node cur = head;
            while (cur != null) {
                if (target == cur.val) {
                    // 说明找到了，就是 cur 目前指向的结点中包含和 target 相等的元素
                    return cur;
                }
                cur = cur.next;
            }

            // 返回一个特殊的引用，表示没有找到
            return null;
        }

        private static List<Node> 查找链表中所有的和某元素相等的结点(Node head, int target) {
            List<Node> ans = new ArrayList<>();
            for (Node cur = head; cur != null; cur = cur.next) {
                if (cur.val == target) {
                    // 找到其中一个
                    ans.add(cur);

                    // 不要返回，继续循环（遍历）查找
                }
            }

            return ans;
        }

        // 链表中至少有 3 个结点
        private static Node 找到链表中的第3个结点(Node head) {
            Node cur = head;

            // 向后跳 2 步
            cur = cur.next;
            cur = cur.next;

            return cur;
        }

        // 链表中至少有 n 个结点
        private static Node 找到链表中的第n个结点(Node head, int n) {
            Node cur = head;
            for (int i = 0; i < n - 1; i++) {
                cur = cur.next;
            }

            return cur;
        }

        // 链表的长度可能小于 n
        // 如果链表长度小于 n，则返回 null 即可
        private static Node 找到链表中的第n个结点但不保证链表长度(Node head, int n) {
            Node cur = head;
            for (int i = 0; i < n - 1 && cur != null; i++) {
                // 此刻 cur 可能是 null，当 cur == null 时，cur.next 就会空指针异常
                cur = cur.next;
            }

            // 两种可能：
            // cur == null：说明链表的长度 < n
            // cur != null，说明，循环了 n - 1 次，找到了第 n 个结点

            return cur; // 两种情况，都可以通过返回 cur 进行处理
        }

        // 链表中至少有 1 个结点
        private static Node 找到链表的倒数第1个结点(Node head) {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }

            return cur;
        }

        // 链表中至少有 2 个结点
        private static Node 找到链表的倒数第2个结点(Node head) {
            Node cur = head;
            while (cur.next.next != null) {
                cur = cur.next;
            }

            return cur;
        }

        // 链表中至少有 3 个结点
        private static Node 找到链表的倒数第3个结点(Node head) {
            Node cur = head;
            while (cur.next.next.next != null) {
                cur = cur.next;
            }

            return cur;
        }

        // 返回值类型暂时使用 void，一会儿要调整
        // 返回值类型定成 Node 引用，是因为我们完成操作之后，需要返回链表的新的头结点，这样调用方法的人，可以拿到最新的链表头结点
        private static Node 头插元素(Node head, int e) {
            // 1) 先把元素装入到对应的结点中
            Node node = new Node(e);

            // 2) 将创建出来的新结点和链表中的结点产生关系
            // 思考：2.1 和 2.2 能否用一套代码就完成？
            // 2.1) 链表是空的（empty）链表，即 head == null
            node.next = head;
            return node;
//        if (head == null) {
//            // node 就是插入完成之后链表的头结点
//            node.next = head;  // 这里 head 是 null
////            node.next = null;
////            head = node;        // head 只是一个形参，修改形参没有意义
//            return node;
//        }
//        // 2.2) 链表不是空的（empty），即 head != null
//        else {
//            node.next = head;
//
//            return node;    // 返回链表中最新的头结点
//        }
        }

        private static Node 头插结点(Node head, Node node) {
            // 把 node 这个孤立的结点，头插到 head 所代表的链表中
            node.next = head;
            return node;
        }

        private static Node 头删(Node head) {
            if (head == null) {
                throw new RuntimeException("链表是空的(empty)，没法删除结点");
            }

            return head.next;

//        if (head.next == null) {
//            // 链表中只有一个头结点
//            return head.next;
//        } else {
//            return head.next;
//        }
        }

        public static void main(String[] args) {
            Node head = null;
            head = 头插元素(head, 1000);    // 这条语句结束之后，head != null
            head = 头插元素(head, 2000);
            head = 头插元素(head, 3000);

            // [3000, 2000, 1000]
            遍历一条链表_打印链表中的每个元素(head);

            head = 头删(head);

//        Node head = 手动去创建结点然后构建链表();
//
//        Node ans = 找到链表的倒数第2个结点(head);

//        Node ans = 找到链表中的第3个结点(head);
//        Node head = null;

//        System.out.println(统计链表中的元素个数(head));

//        遍历一条链表_打印链表中的每个元素(head);

//        for (Node cur = head; cur != null; cur = cur.next) {
//            System.out.println(cur.val);
//        }

//        System.out.println(head);
//        System.out.println(head.val);
   }
}
